Typically a computer application such as 168 in FIG. 1A or an operating system provides a graphic object stream to a device such as a printer 1750 in FIG. 1A for printing and/or display. A graphic object stream is a sequence of graphic objects such as 1801 in FIG. 13 in priority order (also known as z-order). A typical graphic object 1801 comprises a fill path (also referred to simply as a “path” (depicted by a directed dashed line 1802), a fill pattern (depicted by the diagonal line pattern within the fill path 1802), a raster operator ROP, optional clip paths, and other attributes.
A fill path comprises of a plurality of closed paths where each closed path comprises a plurality of x-y coordinate points (also referred to as points) to represent a plurality of curve segments where the endpoint of each curve segment is the starting point of the next curve segment, and the last curve segment's end point is the starting point of the first curve segment. A curve segment can be a linear line segment which is referred as “line segment”. The embodiment can be generalized for other non-linear curve segments such as quadratic Bezier curve segment, cubic curve segment, etc. For example the application may provide a graphic object stream via function calls to a Graphics Device Interface (GDI) layer, such as the Microsoft Windows™ GDI layer. A printer driver for the associated target printer is software that receives the graphic object stream from the GDI layer. For each graphic object, the printer driver is responsible for generating a description of the graphic object in the Page Description Language (PDL) that is understood by the rendering system of the target printer.
In some systems the application 168 or operating system may store the print data generated by the application 168 in a file, referred to as a spool file, in a common well-defined format. The common well-defined format is also called the spool file format. During printing the printer driver receives the spool file, and parses the contents of the file to generate graphic object streams for a Raster Image Processor on the target printer. Examples of spool file formats are Adobe's PDF™ and Microsoft's XPS™.
In order to print a spool file residing on a computer on a target printer, the spool file contents must first be converted to the equivalent graphic object stream for the Raster Image Processor (RIP). A filter module, typically residing in a printer driver, is used to achieve this.
Some current raster image processors use the well-known Pixel-Sequential Rendering (PSR) method to generate raster images. In such arrangements a description of all graphic objects to be drawn are retained in a display list. On each scanline such as 1803, edges such as 1805, 1806 of objects such as 1801 that intersect the scanline 1803 at respective scanline coordinates 1807, 1808 are stored, in the form of corresponding edge records, in a list in increasing scanline-axis order of their intersection with the scanline. These points of intersection 1807, 1808, or edge crossings, are considered by an operative processor in turn, and are used to activate or deactivate objects in the display list. Between each pair of edge crossings considered such as 1807, 1808, colour data for each pixel that lies between the first edge crossing 1807 and the second edge crossing 1808 is generated based on which graphic objects are active for that horizontal span of pixels 1809. This horizontal span of pixels is referred to as “a pixel run”. The distance 1823 between the scanline coordinates 1807, 1808 in the scanline direction 1822 in parallel to x axis is referred to as the pixel run range of the pixel run 1809, or alternately as the range of the pixel run 1809. In preparation for the next scanline, the coordinates of intersection 1807, 1808 of each respective edge 1805, 1806 is updated in accordance with the nature of each edge. New edges are also merged into the list of edges, which is called the active edge list. Any active edges that have expired (i.e. have become inactive) on the current scanline are removed from the active edge list.
Generally computer applications or operating systems generate optimal graphic objects for displaying or printing. Applications that generate non-optimal graphic objects may cause a RIP to stall or fail to properly render a certain data stream. For example if thousands of glyph graphic objects are to be drawn at approximately the same location, there will be many edges and many object activation and deactivation events that will significantly reduce the overall RIP performance. Typically a RIP cannot handle this kind of graphic object stream properly.
In one known RIP system, many graphic objects of similar characteristics within close proximity are detected and combined into a single composite object. The resulting path of the composite object, referred to as a composite path, is a combination of all the paths representing all the objects that are combined to make up the composite object. The resulting composite path generated by the RIP system represents the boundary of the composite object. However when converting this composite path to a display list format, the composite path can generate many edges, which will typically require a considerable amount of memory and may create a performance problem.
In another known RIP system, complex path objects are detected just before they are added to the display list. An object is considered as having complex path either when the object's path has many points in a small region, or when the object is painted using a special raster operation where the object's mask can be represented as the object outline. Once a complex object path is detected, the known RIP system is used to scan-convert the object's path to produce pixel runs such as 1809. Thereafter, adjacent overlapping pixel runs such as 1809, 1810 are joined together with edges 1811-1809-1805 and 1806-1813-1812 thus defining boundaries of the resultant pixel run. This is known as “path tracing” or “edges tracing” or merely as rendering. Current known “path tracing” methods do not produce the minimum number of edges for a particular input path data.